import java.util.Iterator;

public class RandomQueue<Item> implements Iterable<Item> {

	//initializing our collection and sizeCounter
	private Item[] collection;
	int szCount = 0;
	
	// create an empty random queue
	public RandomQueue() {
		collection = (Item[]) new Object[2]; //correct implementation
	}
	
	// is it empty? - checks whether the accesspoint is occupied
	public boolean isEmpty() {
		return szCount == 0;
	}
	
	// return the number of elements in the entire collection
	public int size() {
		return szCount;
	}
	
	//PROPS TO TERRIBAD MIKKEL
	//To avoid iterating over the entire right side of the collection
	//Swaps the "a" index in the array with the last element
	public void swapLast(int a) {
	Item tmp = collection[szCount]; //tmp variable for storing the note to be deleted
	collection[szCount] = collection[a]; //the swap itself
	collection[a] = tmp; //new reference for the last entry
	collection[szCount] = null; //cleaning up the reference
	}
	
	// add an item to the collection
	public void push(Item item) {
		if (szCount == collection.length) resize(2*collection.length);
		collection[szCount++] = item;
	}
	
	 // Move stack of size szCount <= newSize to a new array of size max.
	private void resize(int newSize) {
		Item[] temp = (Item[]) new Object[newSize];
		for (int i = 0; i < szCount; i++)
			temp[i] = collection[i];
		collection = temp;
	}
	
	// return (but do not remove) a random item
	public Item sample() {
		int random = StdRandom.uniform(szCount);
		Item item = collection[random];
		return item;
	}
	
	// remove and return a random item
	public Item pop() {
		int random = StdRandom.uniform(szCount);
		Item item = collection[random];
		swapLast(random);
		if (szCount > 0 && szCount == collection.length/4) resize(collection.length/2);
		--szCount;
		return item;
	}
	
	// return an iterator over the items in random order
	public Iterator<Item> iterator() { return new ListIterator();}
		
	private class ListIterator implements Iterator<Item> {
		private Item[] tmpCol = collection.clone();
		private int elements = szCount-1;
		
	public boolean hasNext(){
		return elements >= 0;
		}
	
	public void remove() {}
	
	public void iteratorSwap(int a) {
		Item tmp = tmpCol[elements+1]; //tmp variable for storing the note to be swapped
		tmpCol[elements+1] = tmpCol[a]; //the swap itself
		tmpCol[a] = tmp; //new reference for the last entry
		}
	
	public Item next() {
		Item item;
		if(elements > 0) {
			int z = StdRandom.uniform(elements--);
			item = tmpCol[z];
			iteratorSwap(z);
		}
		else {
			item = tmpCol[elements--];
			tmpCol = null;
			}
		return item;
		}
	}
	
  public static void main(String args[]) {
    // Build a queue containing the Integers 1,2,...,6:
    RandomQueue<Integer> Q = new RandomQueue<Integer>();
    for (int i = 1; i < 7; ++i)
		Q.push(i); // autoboxing! cool!
 
    // Print 30 die rolls to standard output
    StdOut.print("Some die rolls: ");
    for (int i = 1; i < 30; ++i)
		StdOut.print(Q.sample() +" ");
    StdOut.println();

    // Let's be more serious: do they really behave like die rolls?
    int[] rolls = new int [10000];
    for (int i = 0; i < 10000; ++i)
      rolls[i] = Q.sample(); // autounboxing! Also cool!
    StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
    StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
	StdStats.stddev(rolls));
    
    // Let's look at the iterator. First, we make a queue of colours:
    
    RandomQueue<String> C = new RandomQueue<String>();
    C.push("red"); C.push("blue"); C.push("green"); C.push("yellow"); 

    Iterator I = C.iterator();
    Iterator J = C.iterator();

    StdOut.print("Two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.print(I.next()+" ");
    
    StdOut.print("\nEntire second shuffle: ");
    while (J.hasNext())
		StdOut.print(J.next()+" ");

    StdOut.print("\nRemaining two colours from first shuffle: ");
    StdOut.print(I.next()+" ");
    StdOut.println(I.next());
	sig();
	}
	public static void sig(){
	StdOut.print(
"	     ____________________________________________________\n"+
"            /                                                    \\\n"+
"           |    _____________________________________________     |\n"+
"           |   |                                             |    |\n"+
"           |   |    ||||                                     |    |\n"+
"           |   |     ||                                      |    |\n"+
"           |   |     ||  h e                                 |    |\n"+
"           |   |                                             |    |\n"+
"           |   |           ||||                              |    |\n"+
"           |   |            ||                               |    |\n"+
"           |   |            || e r r i b a d s               |    |\n"+
"           |   |                                             |    |\n"+
"           |   |                                             |    |\n"+
"           |   |               ||||                          |    |\n"+
"           |   |                ||                           |    |\n"+
"           |   |                || r o l o l o l o l o l     |    |\n"+
"           |   |_____________________________________________|    |\n"+
"           |                                                      |\n"+
"            \\_____________________________________________________/\n"+
"                   \\_______________________________________/\n"+
"                _______________________________________________\n"+
"             _-'    .-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.  --- `-_\n"+
"          _-'.-.-. .---.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.--.  .-.-.`-_\n"+
"       _-'.-.-.-. .---.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-`__`. .-.-.-.`-_\n"+
"    _-'.-.-.-.-. .-----.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-----. .-.-.-.-.`-_\n"+
" _-'.-.-.-.-.-. .---.-. .-----------------------------. .-.---. .---.-.-.-.`-_\n"+
":-----------------------------------------------------------------------------:\n"+
"`---._.-----------------------------------------------------------------._.---'\n"
);
}	
}
